package com.lzq.leetcode.lanqiao;

import java.util.Arrays;

public class s1022 {

    public static void main(String[] args) {

        int[][] map = new int[4][4];
        // 初始化
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                map[i][j] = -1;
            }
        }

        int[] sum = new int[]{0};

        dfs(map, 0, sum);

        System.out.println(sum[0]);

    }

    public static void dfs(int[][] map, int node, int[] sum) {

        if (node == 16) {
            //
            ++sum[0];
            return;
        }

        for (int i = 0; i < 16; i++) {
            int x = i / 4;
            int y = i % 4;
            // 判断是否可行
            // 1. 当前位置没有被站
            if (node == 0) {
                map[x][y] = node;
                dfs(map, node + 1, sum);
                map[x][y] = -1;
            } else if (map[x][y] == -1) {
                // 2. 他的上一个节点在他的四周
                if ((x - 1 >= 0 && map[x - 1][y] == node - 1) ||
                        (x + 1 < 4 && map[x + 1][y] == node - 1) ||
                        (y - 1 >= 0 && map[x][y - 1] == node - 1) ||
                        (y + 1 < 4 && map[x][y + 1] == node - 1)) {
                    map[x][y] = node;
                    dfs(map, node + 1, sum);
                    map[x][y] = -1;

                }
            }
        }
    }
}




